#pragma once
#ifndef COSTUM_UTILS_H
#define COSTUM_UTILS_H

#include <iostream>
#include <vector>
#include <stdio.h>

using std::vector;

#ifdef _WIN32
#define CPAUSE getchar()
#endif // _WIN32

template <typename T>
void reset(T &params) { params = 0; }

inline void EXCHANGE(int &fir, int &sec) {
	int temp = fir;
	fir = sec;
	sec = temp;
}

#define INFTY 2147483647l
#define PI 3.1415926

void insertionSorted(vector<int> & list);//O(n^2)
void selectionSorted(vector<int> & list);//O(n^2)
void refinedShellSorted(vector<int> & list);//O(n^2)

//merge sort
void mergeSorted(vector<int> & list, int start, int end);//O(nlgn)

//find the maximum subarray
struct IndexAndMax
{
	int leftIndex; int rightIndex; int maxSum;
	IndexAndMax(int li, int ri, int ms)
		:leftIndex{li},
		rightIndex{ri},
		maxSum{maxSum}
	{}
	void show(void) {
		std::cout << "left: " << leftIndex << ", right: " << rightIndex << ", sum: " << maxSum << std::endl;
	}
};
IndexAndMax findMaxSubarray(int * list, int low, int high);//O(nlogn)
int findMaxSubarray(int *list, int length);//O(n)

//Heap sort
inline int PARENT(int i) { return i / 2; }
inline int LEFT(int i) { return 2 * i + 1; }
inline int RIGHT(int i) { return 2 * i + 2; }
void heapSort(vector<int> &list);//O(nlogn)

//quick sort
void quickSort(vector<int> &list, int begin, int end);//aver: O(nlogn), worsted: O(n^2)

//counting sort, in this way, you must know the maximum number of your array, and the 
//minimum number must equal to zero.
vector<int> countingSort(vector<int> list, int max);//O(n)

//Perlin Noise

float randNumGenerator(int a);
float perlinNoise();


#endif // COSTUM_UTILS_H
